package com.bean;

import java.util.Random;

public class QuickSort {
    private static final String TAG = "QuickSort";
    private int[] numbers;
    private int number;

/*    public void sort(int[] values) {
        // 检查数组是否为空
        if (values == null || values.length == 0) {
            return;
        }
        this.numbers = values;
        number = values.length;
        quicksort(0, number - 1);

    }*/

    public static void quicksort(int a[], int low, int high) {
        int i = low, j = high;
        // 把数组中间的元素设置为基准数
        int pivot = a[low + (high - low) / 2];

        // 分开成两个数组
        while (i <= j) {
            //从左向右“探测”，如果左边的元素小于基准数，则去“探测”下一个元素
            while (a[i] < pivot) {
                i++;
            }
            //从右向左“探测”，如果左边的元素大于基准数，则去“探测”下一个元素
            while (a[j] > pivot) {
                j--;
            }

            // 如果左边探测结果大于基准数，右边探测结果小于基准数，那么交换这两个元素
            // 然后继续探测
            if (i <= j) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                i++;
                j--;
            }
        }
        // 递归
        if (low < j)
            quicksort(a, low, j);
        if (i < high)
            quicksort(a, i, high);
    }

    private void exchange(int i, int j) {
        int temp = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = temp;
    }

    public static void main(String[] args) {
        Random random = new Random();
        int arrays[] = new int[100];
        for (int i = 0; i < 100; i++) {
            arrays[i] = random.nextInt(1000);
        }
        //      int arrays[]=new int[]{15 ,16, 17, 18, 19,    20,    21, 14, 23, 24, 25};
        quicksort(arrays, 0, arrays.length - 1);

        for (int i = 0; i < arrays.length - 1; i++) {
            if (i % 10 == 0) {
                System.out.println(" ");
            }
            System.out.print(arrays[i] + " ");
        }
    }

/*    public static void quickSort(int a[], int low, int high){
        int i=low;
        int j=high;
        int pivot=low+(high-low)/2;				//选取数组中间的元素作为基准值
        while(i<=j){
            while(a[i]<a[pivot]){			// 左指针不断往右边探索，直到找到大于基准值的元素
                i++;
            }
            while(a[j]>a[pivot]){			// 右指针不断往左边探索，直到找到小于基准值的元素
                j--;
            }
            if(i<=j){					// 交换两个元素的位置 并同时往各自的方向前进一格
                int temp=a[i];
                a[i]=a[j];
                a[j]=temp;	//在这种情况中,i>j,i在第二轮26的位置，j在18的位置
                i++;					// {15 16 17 26 18    20    21 22 23 24 25   }
                j--;					// {15 16 17 20 18    26    21 22 23 24 25   }
            }
        }								// {15 16 17 18 19    20    21 14 23 24 25	 }
        if(low<j){						// {15 16 17 18 19    14    21 20 23 24 25   }
            quickSort(a,low,j);
        }
        if(i<high){
            quickSort(a,i,high);
        }
        // 以上两个迭代分别代表着 基准值 左边 和 右边 序列的循环
    }
    public static void main (String[] args){
        Random rd=new Random();
        int[] arrays=new int [100];
        for(int i=0;i<100;i++){
            arrays[i]=rd.nextInt(1000);
        }
        quickSort(arrays,0,arrays.length-1);
        for(int k=0;k<arrays.length-1;k++){
            if(k%10==0){
                System.out.println("");
            }
            System.out.print(arrays[k]+" ");
        }
    }*/

}

